0x01 基础

B+树实际上就是一种特殊的$M$路平衡树，内部节点存储$$键值对，叶子节点存储$$键值对，每个节点不少于$\frac{M}{2}-1$个键值对，不多于$M-1$个键值对 。基于每个节点的大小相对比较固定，B+树可以保证在对数时间内完成查找、删除，同时底层叶子节点顺序连接的特性使其可以顺序扫描叶子节点。

B+树的维护是老生常谈的问题，插入操作需要考虑分裂，删除操作需要考虑合并（$Merge$）。

0x02 特殊情况

B+树中默认叶子节点中的每一个键都是不同的，但是在一些场景下（non-unique index）需要支持重复键。一种支持重复键的方法是在键后加上$RID$（$RID$就是每一个$record$的唯一标识），这样每一个键都是唯一的，查找时通过匹配$$的方式也依然可以找到对应的$key$。另一种方式是使用溢出叶节点（$overflow\ leaf\ node$），如果当前需要插入的键与普通叶节点已有的键存在重叠，将该键放入溢出叶节点中。第一种方式个人感觉比较常见，第二种方式更难以维护一点。

0x03 设计取舍

B+树中有一些设计上的取舍。

首先是每一个节点的大小。如果每一个节点大小非常大，降低了IO次数，但是可能会让较多的查找、删除操作命中同一个节点，造成竞争；如果每一个节点大小很小，会导致在顺序扫描时需要频繁读取页，但是有利于查找操作频繁的场景。

其次是合并的时机。B+树语境下的合并发生在删除过程中， 这个过程实际上可以延后，通过一种类似$LSM$树中的定期紧实（$Compact$）机制来定期重建当前的B+树。

再者是对变长键的支持。最简单的策略就是存储一个指针，指针指向实际的键值。比较完备的策略就是支持每一个节点的长度不同，但是需要更细致的页管理（变长？伙伴算法？）。padding个人感觉是比较naive的方法，需要根据$key$的实际大小分布来决定，如果大量$key$的大小都远小于可能的最大键长度，这个方案就显然不妥。最后一种方法就是类似$slot\ page$的方式，在每一个节点内部引入一个中间映射。

最后是在叶节点内部如何搜索需要的键。常见的方法有线性查找、二分查找，在叶节点页已经读入内存的情况下感觉两者不会有太大差别。如果可以预先获得部分键的分布规律，可以通过插值的方式猜测键的位置，感觉如果结合ML可以在键很多的情况下直接命中键？

0x04 优化

Andy列举了七八种优化的方式，我在这里分成三类来谈。

压缩存储空间

B+树终究是放在磁盘上的数据结构，如果可以让每个叶节点内部存储更多的节点，这对于整体性能毫无疑问有提升。不过还是要看workload，区分究竟是IO密集还是CPU密集。

  • 前缀压缩。leveldb中sstable存储就用了前缀压缩，顺序存储的数据显然存在压缩的可能，如两个字典序相邻的字符串可能只有末尾的几个字符不同
  • 去重。对于non-unique索引，一个键可能对应多个值，此时可以只保留一个键，省下空间
  • 后缀截断。上面两个压缩优化都是针对叶节点的，叶节点压缩需要保证数据无损，但是中间节点呢？中间节点实际上只是起到一个引导的作用，所以可以通过某种策略把后缀去掉，保证能区分数据的同时使用更小的空间
提升读写性能

这个优化就是leanstore提出的pointer swizzling（没想到怎么翻译），在B+树叶节点页已经在内存时，直接让中间节点指向对应的内存而非继续使用$page\ id$，跳过$buffer\ pool\ manager$。leanstore在论文里吐槽了传统的基于$buffer \ pool \ manager$的低效，大部分时间花在查页表和同步上了。如果数据完全可以放在内存，使用pointer swizzling甚至可以媲美内存数据库。

其他

如果已经有了排序好的数据，构建B+树最快的方式就是直接自底向上构建。原来是你，旁路导入。